
class LinkBean:
    data = None
    next = None

    def __init__(self, data):
        self.data = data

    def setNext(self, next):
        self.next = next


class Stack:
    head = None

    def __init__(self):
        self.initStack()

    def initStack(self):
        self.head = LinkBean('HEAD')

    def destroyStack(self):
        self.head = None

    def stackEmpty(self):
        return self.head.next == None

    def push(self, data):
        linkBean = LinkBean(data)
        linkBean.next = self.head.next
        self.head.next = linkBean

    def pop(self):
        if self.stackEmpty():
            return None
        popData = self.head.next
        self.head.next = popData.next
        return popData.data

    def getTop(self):
        if self.stackEmpty():
            return None
        return self.head.next.data

    def test(self):
        stack = Stack()
        stack.push('蓝')
        stack.push('冷')
        stack.push('ran')
        print(stack.getTop())
        print(stack.pop())
        stack.push('然')
        while not stack.stackEmpty():
            print(stack.pop())


def expToPostExp(str):
    strList = str.split(' ')
    result = ''
    stack = Stack()
    print(strList)
    for s in strList:
        if s.isdigit():
            if result=='':
                result=s
            else:
                result = result+' '+s
        elif isPriority(s):
            # print("运算符",s)
            if stack.stackEmpty():
                stack.push(s)
            elif getPriority(s) > getPriority(stack.getTop()):
                stack.push(s)
            else:
                while not stack.stackEmpty() and getPriority(stack.getTop()) >= getPriority(s):
                    result = result+' '+stack.pop()
                stack.push(s)
        elif s == "(":
            stack.push(s)
        elif s == ")":
            while not stack.getTop() == "(":
                if stack.stackEmpty():
                    raise RuntimeError('format error')
                result = result+' '+stack.pop()
            stack.pop()

    while not stack.stackEmpty():
        result = result+' '+stack.pop()

    return result


def getPriority(operator):
    # print('operator===',operator)
    if operator == "+" or operator == "-":
        return 0
    elif operator == "*" or operator == "/":
        return 1
    elif operator == "(":
        return -1


def isPriority(operator):
    if operator == "+" or operator == "-" or operator == "*" or operator == "/":
        return True
    return False


def calculation(postExp):
    postExpList=postExp.strip().split(' ')
    print(postExpList)
    stack=Stack()
    for s in postExpList:
        if s.isdigit():
            stack.push(s)
        else:
            stack.push(calculationTwoValue(stack.pop(),stack.pop(),s))
    # while stack.getTop()!=None:
    #     print('calculation====',stack.pop())
    return stack.pop()

def calculationTwoValue(sa,sb,operator):
    a=int(sa)
    b=int(sb)
    if operator =='+':
        return b+a
    elif operator == '-':
        return b-a
    elif operator=='*':
        return b*a
    elif operator=='/':
        return b/a
    else:
        raise RuntimeError("未知运算符"+operator)

def calculationExp(exp):
    postExp = expToPostExp(exp)
    return calculation(postExp)

# postExp = expToPostExp('1 + 11 + 21')
# print(postExp)
# print(expToPostExp('2 * ( 1 + 3 ) - 4'))
# print(expToPostExp('2 + 9 / 3 - 5'))
# result=calculation(postExp)
# print('result===',result)
print(calculationExp('2 * ( 1 + 3 ) - 4'))
print(calculationExp('2 + 9 / 3 - 5'))
